C++では、コンテナの成長を管理することは、 サイズ （現在の要素数）と キャパシティ （予約済みメモリ）の間で行われるアーキテクチャ上の調整です。連続するコンテナ（例： vector および stringなど）において、キャパシティに達すると 再割り当てが発生します。システムはより大きなメモリブロックを見つけ、すべての要素を移動し、古いブロックを破棄します。これは高コストな$O(n)$処理であり、 イテレータ無効化——以前の要素へのポインタが「ダングリング」状態になり、危険な状態になります。
1. 拡張戦略
頻繁な再割り当てを避けるために、 vector 実装は「バッファ」領域を確保します。 c.reserve(n) コマンドは要素を追加せずに最小キャパシティを明示的に設定します。一方、 c.shrink_to_fit() は、余分なメモリをオペレーティングシステムに返すことを非拘束的な要求として行います。
2. resize と reserve の違い
一方、 reserve reserve はバッファにのみ影響を与えます。 resize(n) resize(n) はコンテナの論理を実際に変更します。縮小する場合、 resize 要素が削除されますが、拡大するとデフォルト初期化された値が追加されます。
⚠️ 警告: もし
resize コンテナが縮小されると、削除された要素へのイテレータは無効になります。拡大により再割り当てが発生した場合、 すべて イテレータはすべて無効になります。main.py
TERMINALbash — 80x24
> Ready. Click "Run" to execute.
>
QUESTION 1
Exercise 9.34: Predict the behavior of this loop: while (iter != vi.end()) { if (*iter % 2) iter = vi.insert(iter, *iter); ++iter; }
It duplicates all odd numbers once and finishes.
It results in an infinite loop if an odd number is found.
It skips all odd numbers.
It causes a compilation error because of iterator types.
✅ Correct!
This is an infinite loop. vi.insert(iter, *iter) inserts before the current element and returns an iterator to the NEW element. The ++iter then moves back to the original odd element, repeating the process forever.❌ Incorrect
Analyze the return value of insert: it points to the newly inserted element. Incrementing once just puts you back on the original element you just processed.QUESTION 2
Exercise 10.10: Why don't generic algorithms like find or sort change the size of containers?
They operate on iterators, which provide no interface to add/remove container memory.
Changing size would be too slow for generic code.
The C++ standard forbids algorithms from using memory.
Algorithms only work on fixed-size arrays.
✅ Correct!
Algorithms are decoupled from containers. They only see iterators and can only modify the values the iterators point to; they cannot call container-specific members like push_back or erase.❌ Incorrect
Recall the 'Iterator Bridge' concept: algorithms use iterators to remain container-agnostic.QUESTION 3
Given vec has 25 elements, what happens if we call vec.resize(100) then vec.resize(10)?
Size becomes 100, then drops to 10; capacity likely stays at 100 throughout.
Size becomes 100, then 10; capacity drops to 10 immediately.
The program crashes on the second resize.
The elements from index 10-99 are moved to a temporary buffer.
✅ Correct!
resize(100) adds 75 default-initialized elements. resize(10) destroys the last 90 elements, but the allocated capacity remains 100 unless shrink_to_fit is called.❌ Incorrect
Resize shrinks the 'size', but capacity does not shrink automatically to save performance.QUESTION 4
What restriction is placed on the element type when calling the single-argument version of resize?
It must be a primitive type (int, double, etc.).
It must have a default constructor.
It must have a copy constructor.
It cannot be a const type.
✅ Correct!
Since resize(n) creates new elements to reach size n, those elements must be initialized using a default constructor.❌ Incorrect
If we don't provide an initial value, the container must know how to build a 'default' one.QUESTION 5
Exercise 10.39: What kind of iterator does a list have versus a vector?
List: Forward; Vector: Random-access
List: Bidirectional; Vector: Random-access
Both have Random-access iterators.
List: Output; Vector: Input
✅ Correct!
std::list is a doubly-linked list supporting bidirectional movement. std::vector is an array supporting pointer-like arithmetic (Random-access).❌ Incorrect
Can you do 'it + 5' on a list? No, which means it isn't random-access.Case Study: Safe Iterator Loops
Managing Growth in Real-time Applications
You are processing a vector of integers. For every odd number, you must duplicate it. You also need to maintain efficiency and avoid segmentation faults caused by container reallocation during the loop.
Q
1. Re-implement Exercise 9.34 correctly to avoid the infinite loop and handle iterator invalidation.
Solution:
To fix the loop: iter = vi.begin(); while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); iter += 2; } else { ++iter; } } This works because insert returns the iterator to the new element; we advance past both the new and original elements to find the next candidate.
To fix the loop: iter = vi.begin(); while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); iter += 2; } else { ++iter; } } This works because insert returns the iterator to the new element; we advance past both the new and original elements to find the next candidate.
Q
2. Rewrite the duplicate word elimination logic from § 10.2.3 to use a list instead of a vector. What changes?
Solution:
Since list does not support random-access, we cannot use generic sort. We must use lst.sort() and lst.unique() member functions. Unlike the vector version, lst.unique() actually removes elements from the list, changing its size immediately without needing a separate erase call.
Since list does not support random-access, we cannot use generic sort. We must use lst.sort() and lst.unique() member functions. Unlike the vector version, lst.unique() actually removes elements from the list, changing its size immediately without needing a separate erase call.
Q
3. Exercise 10.19: Rewrite the biggies logic to use stable_partition instead of find_if to maintain original order.
Solution:
auto wc = stable_partition(words.begin(), words.end(), [sz](const string &s) { return s.size() >= sz; }); This reorders the container such that all elements meeting the criteria come first, returning an iterator to the first element that does NOT meet the criteria.
auto wc = stable_partition(words.begin(), words.end(), [sz](const string &s) { return s.size() >= sz; }); This reorders the container such that all elements meeting the criteria come first, returning an iterator to the first element that does NOT meet the criteria.